import java.util.List;

/*
 * @author zzr
 * @date: 2025/03/16  18:31
 * @description:单向不带头非循环链表的模拟实现
 */
public class MySingleList {
    static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;
    public int usedSize;

    /**
     * 创建一个链表
     */
    public void createList() {

        ListNode node1 = new ListNode(12);
        ListNode node2 = new ListNode(23);
        ListNode node3 = new ListNode(34);
        ListNode node4 = new ListNode(45);
        ListNode node5 = new ListNode(56);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        head = node1;
    }

    /**
     * 打印链表
     */
    public void display() {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    /**
     * 得到链表长度
     * @return
     */
    public int size() {
        int count = 0;
        ListNode cur = head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    /**
     * 链表中是否包含值为val的节点
     * @param val
     * @return
     */
    public boolean contains(int val) {
        ListNode cur = head;
        while (cur != null) {
            if(val == cur.val) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    /**
     * 链表的头插法
     * @param val
     */
    public void addFirst(int val) {
        ListNode listnode = new ListNode(val);
        listnode.next = head;
        head = listnode;
        usedSize++;
    }

    //有了addFirst方法，也就可以想ArrayList一样 定义一个usedSize，添加一个元素
    //usedSize++ 再求取链表长度的时候 直接return usedSize 不需要遍历链表了
    public int size2() {
        return this.usedSize;
    }

    /**
     * 尾插法
     * @param val
     */
    public void addLast(int val) {

        ListNode listNode = new ListNode(val);

        if(head == null) {
            head = listNode;
            return;
        }
        ListNode cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = listNode;
        usedSize++;
    }

    /**
     * 在指定下标index位置插入值为val的节点 --- version 1.0
     */
//    public void addIndex(int index, int val) {
//
//        ListNode listNode = new ListNode(val);
//        ListNode cur = head;
//        for (int i = 0; i < index - 1; i++) {
//            cur = cur.next;
//        }
//        listNode.next = cur.next;
//        cur.next = listNode;
//        usedSize++;
//    }

    /**
     * 在指定下标index位置插入值为val的节点 version 2.0
     */
//    public void addIndex(int index, int val) {
//
//        if(index < 0 || index > usedSize) {
//            throw new IndexOutOfException(index + "位置不合法");
//        }
//
//        if(index == 0) {
//            addFirst(val);
//            return;
//        }
//        if(index == usedSize) {
//            addLast(val);
//            return;
//        }
//
//        ListNode listNode = new ListNode(val);
//        ListNode cur = head;
//        for (int i = 0; i < index - 1; i++) {
//            cur = cur.next;
//        }
//        listNode.next = cur.next;
//        cur.next = listNode;
//    }

    /**
     * 在指定位置index处 添加值为val的节点 version：3.0(final)
     * @param index
     * @param val
     */
    public void addIndex(int index, int val) {
        checkIndexForAddIndex(index);

        if(0 == index) {
            addFirst(val);
            return;
        }
        if(usedSize == index) {
            addLast(val);
            return;
        }

        ListNode listNode = new ListNode(val);
        ListNode cur = findIndexSubOne(index);

        listNode.next = cur.next;
        cur.next = listNode;
        usedSize++;
    }

    private ListNode findIndexSubOne(int index) {
        ListNode cur = head;
        for (int i = 0; i < index - 1; i++) {
            cur = cur.next;
        }
        return cur;
    }

    private void checkIndexForAddIndex(int index) {
        if (index < 0 || index > usedSize) {
            throw new IndexOutOfException(index + "位置不合法");
        }
    }

    private ListNode searchPrev(int key) {

        ListNode cur = head;
        while (cur != null) {
            // 从第二个节点开始查找的
            if(cur.next.val == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    /**
     * 删除第一个遇到的 值为key的元素
     * @param key
     */
    public void remove(int key) {

        if(head == null) {
            throw new LinkedListIsEmptyException("该链表为空，无法进行删除操作");
        }
        //单独检查头节点
        if (key == head.val) {
            head = head.next;
            return;
        }
        ListNode prevNode = searchPrev(key);
        if (null == prevNode) {
            System.out.println("找不到该元素");
            return;
        }
        ListNode del = prevNode.next;
        prevNode.next = del.next;
        usedSize--;
    }

    /**
     * 删除所有值为key的节点
     * @param key
     */
    public void removeAll(int key) {

        if (head == null) {
            return;
        }
        while(head != null && key == head.val) {
            head = head.next;
        }

        ListNode prev = head;
        ListNode cur = head.next;

        while(cur != null) {
            if(cur.val == key) {
                prev.next = cur.next;
                cur = cur.next;
            } else {
                prev = cur;
                cur = cur.next;
            }
        }
    }

    /**
     * 清空链表
     */
    public void clear() {
        this.head = null;
        usedSize = 0;
    }
}
